When a party receives a message or a data file (both referred to as messages hereinafter) this receiving party may wish to verify the integrity of the message to verify that the message has not been tampered with since it left the possession of the sending party, to verify the authenticity of the message, and to the prevent later repudiation by the sending party. Digital signatures are a known technology that satisfy all three reasons for verifying message integrity.
Most known digital signature systems use public key signature systems, where a digital signature is a number that is generated by the signing party with an algorithm that uses as input the content of the message and one or more secret numbers, known as the private keys of the system. One or more public keys are generated by the signing party and made known to the verifying party, whom may use them in combination with the signature to verify the message's integrity. A third party, trusted by both the sending and receiving parties, may certify the public keys as bound to the identity of the signing party. Once in possession of a certified public key, the verifying party can verify that a message sent with a signature was in fact sent by the party whom the public key was certified to and can verify that the message was not altered since it was signed.
The security of public key signature systems is not absolute, but such systems may be designed to be computationally secure. Computationally secure systems have theoretical vulnerabilities which a hypothetical forger could exploit, but the level of computational resources required to do so are judged to be far beyond those available to the hypothetical forger. Computationally secure systems often rely on the difficulty of solving certain mathematical problems. For example, the widely used Rivest—Shamir—Adlemen (RSA) signature scheme depends on the difficulty of factoring large integers. In the RSA scheme, the message signer/sender selects two large, distinct, prime numbers p and q. One of the public keys n, is product of the private keys p and q. The other public key e, is determined by the sender first computing the totient:φ(n)=(p−1)(q−1)  Equation 1
The sender then chooses an integer e such that:1<e<φ(n) and e coprime to φ(n)  Equations 2a and 2b
The sender's private key d may then be determined by choosing an integer d such that:1<d<φ(n) and ed≡1(mod φ(n))  Equations 3a and 3b
The sender can then generate a signature for a message m by computing:s=md mod n  Equation 4
With the public keys n and e, the verifying party can recover the message by computing:m=se mod n  Equation 5Solving Equations 1-4 is computationally feasible with known algorithms for parties in possession of the private keys p, q, and d. Solving the RSA verification formula (Equation 5) is computationally feasible with known algorithms for parties in possession of public keys e and n. However, to forge a signature using public key n without knowing the private key d requires the forger to factor the public key n or use some other method as equally difficult. This task can be made computationally infeasible if p and q are judiciously picked. Primarily, p and q should be large enough to overwhelm the factoring methods and computational resources available to potential forgers.
While making it more difficult for potential forgers, large p, q and e values may also increase the computational time for legitimate senders to generate signatures and receivers of signed messages to verify messages. For example, a currently typical RSA scheme may have public keys n=2048, and e=17. These values would require the RSA message verification formula (Equation 5) to perform 4 modular squares and 1 modular multiplication. Implementations of this example on current computer hardware will consume ˜15 million core clock cycles and the time required falls in the millisecond scale.
Another known digital signature system is the Rabin signature scheme. Similar to the RSA scheme, the Rabin scheme starts with generating a public key N, which is product of P and Q, two large, distinct, prime numbers. However, the exponent in the Rabin message verification formula does not have to be odd and is usually set to 2:M=S2 mod N  Equation 6
The Rabin signature generation formula uses ½ for the exponent:S=M1/2 mod N  Equation 7The use of ½ as an exponent requires that message M be a quadratic residue modulo N. Stated differently, to create a Rabin signature there should exist a square root for the message M in modular arithmetic when the modulus is N. This will not be true for all messages that a sender may desire to send, so an additional stage may be used to transform any message that is not a quadratic residue modulo N to into a value that is. If one knows the values of the factors of N, (i.e. P and Q), efficient algorithms exist for solving the Rabin signature generation formula (Equation 7). However, with a judicious selection of N, the Rabin signature generation formula (Equation 7) can be made computationally infeasible for parties that do not possess the values of the factors of N, (i.e. P and Q).
The verification process of a Rabin signature system can require less computation than a similar RSA signature system. This is primarily due to the fact that modular squares may be performed more efficiently than modular multiplication. The RSA scheme with its odd exponents requires at least one modular multiplication. For example, to perform an RSA signature verification (Equation 5) with e=3 one modular square and one modular multiplication are performed. To perform a similar Rabin verification with e=2, only a modular square is performed. Even though the Rabin verification may be computed faster than a similar RSA verification, it still has the disadvantage of using modular arithmetic, which generally requires more computation time than regular, non-modular arithmetic.